/**
 * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合
 * @param {string} digits 
 * @returns 
 */
// 回溯法 类似78.子集
var letterCombinations = function (digits) {
    if (digits.length == 0) {
        return []
    }
    const phoneMap = {
        2: "abc",
        3: "def",
        4: "ghi",
        5: "jkl",
        6: "mno",
        7: "pqrs",
        8: "tuv",
        9: "wxyz",
    }
    // 中间结果
    combination = []
    // 最终结果
    combinations = []

    var backtrack = function (index) {
        if (index == digits.length) {
            // 终止条件
            combinations.push(combination.join(""))
        } else {
            // 当前数字
            let digit = digits[index]
            // 当前数字对应的字母
            for (let letter of phoneMap[digit]) {
                // ad->ae->af->bd->be->bf->cd->ce->cf
                combination.push(letter)
                backtrack(index + 1)
                combination.pop()
            }
        }
    }

    backtrack(0)
    return combinations
}
